/**
 * 
 */
package leetCode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
import java.util.TreeMap;

/**
 * @author zhongfang
 *
 */
public class NumberofAtoms {
	public String countOfAtoms(String formula) {
		HashMap<Integer, Integer> paIndex = new HashMap<>();
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < formula.length(); i++) {
			if (formula.charAt(i) == '(') {
				stack.push(i);
			} else if (formula.charAt(i) == ')') {
				int left = stack.pop();
				paIndex.put(left, i);
			}
		}
		Map<String, Integer> atom2Freq = countOfAtoms(formula.toCharArray(), 0, formula.length() - 1, paIndex);
		StringBuilder reStringBuilder = new StringBuilder();
		for (String string : atom2Freq.keySet()) {
			reStringBuilder.append(string);
			int count = atom2Freq.get(string);
			if (count != 1) {
				reStringBuilder.append(count);
			}
		}
		return reStringBuilder.toString();
	}

	private Map<String, Integer> countOfAtoms(char[] formula, int start, int end, Map<Integer, Integer> paIndex) {
		Map<String, Integer> res = new TreeMap<>();
		int i = start;
		while (i <= end) {
			if (formula[i] == '(') {
				int rightIndex = paIndex.get(i);
				Map<String, Integer> freq = countOfAtoms(formula, i + 1, rightIndex - 1, paIndex);// 递归获取内部的数量
				i = rightIndex + 1;// 下一个待处理的位置是右括号之后
				int count = 1;
				// 若右括号之后是数字
				if (i < formula.length && Character.isDigit(formula[i])) {
					int[] c = getCount(formula, i);
					count = c[0];
					i = c[1];// 数字结束的位置
				}
				// 合并到当前res里面
				for (String atom : freq.keySet()) {
					res.put(atom, res.getOrDefault(atom, 0) + freq.get(atom) * count);
					// if (res.containsKey(atom)) {
					// res.put(atom, res.get(atom) + freq.get(atom) * count);
					// } else {
					// res.put(atom, freq.get(atom) * count);
					// }
				}
			} else {
				int nameStart = i;
				i++;
				while (i < formula.length && Character.isLowerCase(formula[i])) {
					i++;
				}
				String name = new String(formula, nameStart, i - nameStart);// 元素名称
				int count = 1;
				if (i < formula.length && Character.isDigit(formula[i])) {
					int[] c = getCount(formula, i);
					count = c[0];
					i = c[1];
				}
				// if (res.containsKey(name)) {
				// res.put(name, res.get(name) + count);
				// } else {
				// res.put(name, count);
				// }
				res.put(name, res.getOrDefault(name, 0) + count);
			}
		}
		return res;
	}

	private int[] getCount(char[] formula, int countIndex) {
		int count = 0;
		while (countIndex < formula.length && Character.isDigit(formula[countIndex])) {
			count *= 10;
			count += formula[countIndex] - '0';
			countIndex++;
		}
		return new int[] { count, countIndex };
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String formula = "Mg(OH)2";
		System.out.println(new NumberofAtoms().countOfAtoms(formula));
	}

}
